#ifndef CanalSAT_Nodeparallel_h
#define CanalSAT_Nodeparallel_h

#define NB_THREADS_PER_BLOCK 8

struct NodeParallel
{
	char *bitmap, *b1, *b2, *b3, *b4;
	int n, m, o;
};


/*
 * Int queue
 */

/**
 * A structure defining a fixed maximum size queue containing integers.
 */
struct QueueInt
{
	/** The pointer to the memory space storing the queue. */
	int * queue;
	/** The current size of the queue. */
	size_t size;
	/** The maximum size of the queue (in number of elements). */
	size_t max_size;
	/** The start index of the queue (index of the first element). */
	size_t start;
	/** The end index of the queue (index just after the last element). */
	size_t end;
};

/**
 * Create a new queue.
 *
 * @param queue A pointer to the memory space where to store the queue.
 * @param max_size The maximum size of the queue (in number of elements).
 * @return The newly created queue.
 */
__device__ inline QueueInt newQueueInt (int * queue, size_t max_size)
{
	QueueInt q;
	q.queue = queue;
	q.size = 0;
	q.max_size = max_size;
	q.start = 0;
	q.end = 0;
	
	return q;
}

/**
 * Check if a queue is empty or not.
 *
 * @param q The queue to check for emptiness.
 * @return True if the queue is empty, false if not.
 */
__device__ inline bool isEmpty (const QueueInt & q)
{
	return q.size == 0;
}

/**
 * Add an element at the end of the queue, provided it isn't already full.
 *
 * @param q The queue to which to add the element.
 * @param value The value of the element to add.
 */
__device__ inline void add (QueueInt & q, int value)
{
	if (q.size < q.max_size)
	{
		q.queue[q.end] = value;
		q.end = (q.end + 1) % q.max_size;
		q.size++;
	}
}

/**
 * Get the value of the first element of a queue and remove it.
 *
 * @param q The queue from which to get the first element.
 * @return The value of the first element.
 */
__device__ inline int poll (QueueInt & q)
{
	int value = q.queue[q.start];
	q.start = (q.start + 1) % q.max_size;
	q.size--;

	return value;
}


/*
 * Bool queue
 */

/**
 * A structure defining a fixed maximum size queue containing booleans.
 */
struct QueueBool
{
	/** The pointer to the memory space storing the queue. */
	bool * queue;
	/** The current size of the queue. */
	size_t size;
	/** The maximum size of the queue (in number of elements). */
	size_t max_size;
	/** The start index of the queue (index of the first element). */
	size_t start;
	/** The end index of the queue (index just after the last element). */
	size_t end;
};

/**
 * Create a new queue.
 *
 * @param queue A pointer to the memory space where to store the queue.
 * @param max_size The maximum size of the queue (in number of elements).
 * @return The newly created queue.
 */
__device__ inline QueueBool newQueueBool (bool * queue, size_t max_size)
{
	QueueBool q;
	q.queue = queue;
	q.size = 0;
	q.max_size = max_size;
	q.start = 0;
	q.end = 0;
	
	return q;
}

/**
 * Check if a queue is empty or not.
 *
 * @param q The queue to check for emptiness.
 * @return True if the queue is empty, false if not.
 */
__device__ inline bool isEmpty (const QueueBool & q)
{
	return q.size == 0;
}

/**
 * Add an element at the end of the queue, provided it isn't already full.
 *
 * @param q The queue to which to add the element.
 * @param value The value of the element to add.
 */
__device__ inline void add (QueueBool & q, bool value)
{
	if (q.size < q.max_size)
	{
		q.queue[q.end] = value;
		q.end = (q.end + 1) % q.max_size;
		q.size++;
	}
}

/**
 * Get the value of the first element of a queue and remove it.
 *
 * @param q The queue from which to get the first element.
 * @return The value of the first element.
 */
__device__ inline bool poll (QueueBool & q)
{
	bool value = q.queue[q.start];
	q.start = (q.start + 1) % q.max_size;
	q.size--;

	return value;
}


/*
 * Parallel bitmap
 */

/**
 * A structure defining a fixed size bitmap.
 */
struct Bitmap
{
	/** The pointer to the memory space storing the bitmap. */
	char * map;
	/** The size of the bitmap. */
	size_t size;
	/** The real size of the allocated memory space. */
	size_t allocated_size;
};

/**
 * Create a new bitmap and initialize all its bits to false.
 *
 * @param map A pointer to the memory space where to store the bitmap.
 * @return The newly created bitmap.
 */
__device__ inline Bitmap newBitmap (char * map, size_t size)
{
	Bitmap b;
	b.map = map;
	b.size = size;
	b.allocated_size = size % 8 == 0 ? size / 8 : size / 8 + 1;

	for (size_t i = 0; i < b.allocated_size; i++)
	{
		map[i] = 0;
	}

	return b;
}

/**
 * Get the value of a bit in a bitmap.
 *
 * @param b The bitmap from which to get the bit value.
 * @param i The index of the bit in the bitmap.
 * @return The boolean value of the considered bit.
 */
__device__ inline bool get (const Bitmap & b, int i)
{
	return *(b.map + i / 8) & (1 << i % 8);
}

/**
 * Set the value of a bit in a bitmap.
 *
 * @param b The bitmap in which to modify the value of a bit.
 * @param i The index of the bit in the bitmap.
 * @param val The new value to give to this bit.
 */
__device__ inline void setBitmap (const Bitmap & b, int i, bool val)
{
	if (get(b, i) != val)
	{
		*(b.map + i / 8) ^= (1 << i % 8);
	}
}

#endif
